/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/merge-two-sorted-interval-lists
   @Language: C++
   @Datetime: 19-04-28 11:22
   */

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
	void merge(vector<Interval> &vi, Interval &a){
		if(vi.size() && vi.back().end>=a.start)
			vi.back().end=max(vi.back().end,a.end);
		else vi.push_back(a);
	}
public:
	/**
	 * @param list1: one of the given list
	 * @param list2: another list
	 * @return: the new sorted list of interval
	 */
	vector<Interval> mergeTwoInterval(vector<Interval> &list1, vector<Interval> &list2) {
		// write your code here
		if(list1.size()==0) return list2;
		if(list2.size()==0) return list1;
		vector<Interval> vi;
		for(int i=0, j=0; i<list1.size() || j<list2.size();){
			if(i>=list1.size() || list1[i].start>list2[j].start)
				merge(vi,list2[j++]);
			else if(j>=list1.size() || list1[i].start<list2[j].start)
				merge(vi,list1[i++]);
			else {
				Interval tmp(list1[i].start, max(list1[i].end,list2[j].end));
				++i, ++j;
				merge(vi,tmp);
			}
		}
		return vi;
	}
};
